#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr) {
            return false;
        }

        ListNode* left = head;
        ListNode* right = head;

        while (right && right->next) {
            left = left->next;
            right = right->next->next;

            if (left == right) {
                return true;
            }
        }
        return false;
    }

    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr;

        ListNode *slow = head;
        ListNode *fast = head;

        // 阶段一：判断是否有环
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {  // 相遇，有环
                // 阶段二：寻找环的入口
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow; // 或 fast，二者相等
            }
        }
        return nullptr; // 无环
    }
};